package cn.antblog.leetcode.array;

/**
 * @author ：YangJingyi
 * @date ：Created in 2022/2/16 11:37
 * @description：二分查找
 * @modified By：
 * @version: 1.0
 */
public class BinarySearch {

    //给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
    //示例 1:
    //输入: nums = [-1,0,3,5,9,12], target = 9
    //输出: 4
    //解释: 9 出现在 nums 中并且下标为 4
    //示例 2:
    //输入: nums = [-1,0,3,5,9,12], target = 2
    //输出: -1
    //解释: 2 不存在 nums 中因此返回 -1
    //提示：
    //你可以假设 nums 中的所有元素是不重复的。
    //n 将在 [1, 10000]之间。
    //nums 的每个元素都将在 [-9999, 9999]之间。

    static final int [] arr1 = {-1,0,3,5,9,12};
    static final int target1 = 9;

    /**
     * 穷举法
     * @return
     */
    public static int method1(){

        //如果小于0 直接返回-1
        if(arr1.length<=0){
            return -1;
        }
        for (int i = 0; i < arr1.length; i++) {
            if(arr1[i] == target1){
                return i;
            }
        }
        return -1;
    }


    /**
     * 二分查找
     * @return
     */
    public static int method2(){

        // 避免当 target 小于nums[0] nums[nums.length - 1]时多次循环运算
        if (target1 < arr1[0] || target1 > arr1[arr1.length - 1]) {
            return -1;
        }

        int left = 0;
        int right = arr1.length-1;

        while (left<=right){
            int middle = left + ((right - left) >> 1);// 防止溢出 等同于(left + right)/2
            if (arr1[middle] > target1){
                right = middle -1;
            }else if(arr1[middle] < target1){
                left = middle + 1; // target 在右区间，所以[middle + 1, right]
            }else {
                return middle;
            }
        }
        return -1;
    }



    public static void main(String[] args) {
//        int i = method2();
//        System.out.println(i);
    }

}
